package leetcode.code0887;

public class Solution extends Solution887 {

	@Override
	public int superEggDrop(int k, int n) {
		return this.superEggDrop(k, 1, n);
	}

	private Integer superEggDrop(int k, int begin, int end) {
		if (begin == end) {
			return 1;
		}
		Integer broke1 = null;
		if (k > 1) {
			for (int i = begin; i <= end; i++) {
				Integer try1 = this.superEggDrop(k - 1, begin, i - 1);
				if (try1 != null) {
					broke1 = broke1 == null ? try1 : Math.min(try1, broke1);
				}
			}
		}
		Integer broke2 = null;
		for (int i = begin; i <= end; i++) {
			Integer try2 = this.superEggDrop(k, i + 1, end);
			if (try2 != null) {
				broke2 = broke2 == null ? try2 : Math.min(try2, broke2);
			}
		}
		if (broke1 == null && broke2 == null)
			return null;
		if (broke1 != null && broke2 != null)
			return Math.max(broke1, broke2) + 1;
		return broke1 == null ? broke2 + 1 : broke1 + 1;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
//		so.debug1();
		so.debug2();
//		so.debug3();
//		so.debug4();
	}

}
